/*
 * @Author: your name
 * @Date: 2022-04-07 11:36:15
 * @LastEditTime: 2022-04-07 13:10:59
 * @LastEditors: Please set LastEditors
 * @Description: 打开koroFileHeader查看配置 进行设置: https://github.com/OBKoro1/koro1FileHeader/wiki/%E9%85%8D%E7%BD%AE
 * @FilePath: /comic-algorithm/chapter05/5.4.js
 */
/**
|--------------------------------------------------
| 求最大公约数
   
  比如 10 和 25 最大公约数等于 25 ÷ 10 商2 余5 
  递归 5 和 10 的最大公约数 10 ÷ 5 商 2 余0
  结束条件 2个数被整除 或者 期中一个数减到1
|--------------------------------------------------
*/
function gcd(a, b) {
  if (a === b) return a;

  //判断 a是奇数还是 偶数
  //采用-更相减损术欧几里得算法
  if ((a & 1) == 0 && (b & 1) == 0) {
    return gcd(a >> 1, b >> 1) << 1;
  } else if ((a & 1) == 0 && (b & 1) != 0) {
    return gcd(a >> 1, b);
  } else if ((a & 1) != 0 && (b & 1) == 0) {
    return gcd(a, b >> 1);
  } else {
    //采用-更相减损术
    let big = a > b ? a : b;
    let small = a < b ? a : b;
    return gcd(big - small, small);
  }
}
